/**
 * @ClassName: 堆排序
 * @author:
 * @Description:
 * @Date
 **/
public class HeapSort {
    private HeapSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] data) {
        MaxHeap<E> maxHeap = new MaxHeap<>();
        for (E e : data) {
            maxHeap.add(e);
        }
        for (int i = data.length - 1; i >= 0; i--) {
            data[i] = maxHeap.extractMax();
        }
    }

    public static <E extends Comparable<E>> void sort2(E[] data) {
        if (data.length <= 1) return;
        //从第一个非叶子节点开始
        for (int i = (data.length - 2) / 2; i >= 0; i--) {
            //下沉元素
            siftDown(data, i, data.length);
        }

        for (int i = data.length - 1; i >= 0; i--) {
            swap(data, 0, i);
            siftDown(data, 0, i);
        }
    }

    //对data[0,n)所形成的最大堆中，索引i的元素，执行siftDown
    private static <E extends Comparable<E>> void siftDown(E[] data, int i, int n) {

        while ((2 * i) + 1 < n) {
            //在此轮循环中，data[i]和data[j]交换位置
            int j = 2 * i + 1;
            if (j + 1 < n && data[j + 1].compareTo(data[j]) > 0) {
                j++;
                //data[j]是leftChild和rightChild中的最大值
            }
            if (data[i].compareTo(data[j]) >= 0) {
                break;
            }
            swap(data, i, j);
            i = j;
        }
    }

    public static <E> void swap(E[] data, int i, int j) {
        if (i < 0 || i >= data.length || j < 0 || j <= data.length) {
            throw new IllegalArgumentException("index out of bound");
        }
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

}
